
/*-------------------------------------------------------------------------
 *
 * spgkdtreeproc.c
 *	  k-d 树在 SP-GiST 中的实现
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *			src/backend/access/spgist/spgkdtreeproc.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "access/spgist.h"
#include "access/spgist_private.h"
#include "access/stratnum.h"
#include "catalog/pg_type.h"
#include "utils/builtins.h"
#include "utils/float.h"
#include "utils/geo_decls.h"


Datum spg_kd_config(PG_FUNCTION_ARGS)
{
	/* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
	spgConfigOut *fc_cfg = (spgConfigOut *) PG_GETARG_POINTER(1);

	fc_cfg->prefixType = FLOAT8OID;
	fc_cfg->labelType = VOIDOID;	/* 我们不需要节点标签 */
	fc_cfg->canReturnData = true;
	fc_cfg->longValuesOK = false;
	PG_RETURN_VOID();
}

static int fc_getSide(double fc_coord, bool fc_isX, Point *fc_tst)
{
	double		fc_tstcoord = (fc_isX) ? fc_tst->x : fc_tst->y;

	if (fc_coord == fc_tstcoord)
		return 0;
	else if (fc_coord > fc_tstcoord)
		return 1;
	else
		return -1;
}

Datum spg_kd_choose(PG_FUNCTION_ARGS)
{
	spgChooseIn *fc_in = (spgChooseIn *) PG_GETARG_POINTER(0);
	spgChooseOut *fc_out = (spgChooseOut *) PG_GETARG_POINTER(1);
	Point	   *fc_inPoint = DatumGetPointP(fc_in->datum);
	double		fc_coord;

	if (fc_in->allTheSame)
		elog(ERROR, "allTheSame should not occur for k-d trees");

	Assert(fc_in->hasPrefix);
	fc_coord = DatumGetFloat8(fc_in->prefixDatum);

	Assert(fc_in->nNodes == 2);

	fc_out->resultType = spgMatchNode;
	fc_out->result.matchNode.nodeN =
		(fc_getSide(fc_coord, fc_in->level % 2, fc_inPoint) > 0) ? 0 : 1;
	fc_out->result.matchNode.levelAdd = 1;
	fc_out->result.matchNode.restDatum = PointPGetDatum(fc_inPoint);

	PG_RETURN_VOID();
}

typedef struct SortedPoint
{
	Point	   *p;
	int			i;
} SortedPoint;

static int fc_x_cmp(const void *fc_a, const void *fc_b)
{
	SortedPoint *fc_pa = (SortedPoint *) fc_a;
	SortedPoint *fc_pb = (SortedPoint *) fc_b;

	if (fc_pa->p->x == fc_pb->p->x)
		return 0;
	return (fc_pa->p->x > fc_pb->p->x) ? 1 : -1;
}

static int fc_y_cmp(const void *fc_a, const void *fc_b)
{
	SortedPoint *fc_pa = (SortedPoint *) fc_a;
	SortedPoint *fc_pb = (SortedPoint *) fc_b;

	if (fc_pa->p->y == fc_pb->p->y)
		return 0;
	return (fc_pa->p->y > fc_pb->p->y) ? 1 : -1;
}


Datum spg_kd_picksplit(PG_FUNCTION_ARGS)
{
	spgPickSplitIn *fc_in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
	spgPickSplitOut *fc_out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
	int			fc_i;
	int			fc_middle;
	SortedPoint *fc_sorted;
	double		fc_coord;

	fc_sorted = palloc(sizeof(*fc_sorted) * fc_in->nTuples);
	for (fc_i = 0; fc_i < fc_in->nTuples; fc_i++)
	{
		fc_sorted[fc_i].p = DatumGetPointP(fc_in->datums[fc_i]);
		fc_sorted[fc_i].i = fc_i;
	}

	qsort(fc_sorted, fc_in->nTuples, sizeof(*fc_sorted),
		  (fc_in->level % 2) ? fc_x_cmp : fc_y_cmp);
	fc_middle = fc_in->nTuples >> 1;
	fc_coord = (fc_in->level % 2) ? fc_sorted[fc_middle].p->x : fc_sorted[fc_middle].p->y;

	fc_out->hasPrefix = true;
	fc_out->prefixDatum = Float8GetDatum(fc_coord);

	fc_out->nNodes = 2;
	fc_out->nodeLabels = NULL;		/* 我们不需要节点标签 */

	fc_out->mapTuplesToNodes = palloc(sizeof(int) * fc_in->nTuples);
	fc_out->leafTupleDatums = palloc(sizeof(Datum) * fc_in->nTuples);

	/*
	 * 注意：坐标正好等于coord的点可能会被分类到任一节点，具体取决于它们在排序列表中的位置。
	 * 只要inner_consistent函数能够对这种情况同时向两侧进行搜索，这样是可以的。
	 * 这比试图保持精确边界要好，因为即使我们有许多相同点值的实例，这也能保持树的平衡。
	 * 所以我们永远不应该触发allTheSame逻辑。
	 */
	for (fc_i = 0; fc_i < fc_in->nTuples; fc_i++)
	{
		Point	   *fc_p = fc_sorted[fc_i].p;
		int			fc_n = fc_sorted[fc_i].i;

		fc_out->mapTuplesToNodes[fc_n] = (fc_i < fc_middle) ? 0 : 1;
		fc_out->leafTupleDatums[fc_n] = PointPGetDatum(fc_p);
	}

	PG_RETURN_VOID();
}

Datum spg_kd_inner_consistent(PG_FUNCTION_ARGS)
{
	spgInnerConsistentIn *fc_in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
	spgInnerConsistentOut *fc_out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
	double		fc_coord;
	int			fc_which;
	int			fc_i;
	BOX			fc_bboxes[2];

	Assert(fc_in->hasPrefix);
	fc_coord = DatumGetFloat8(fc_in->prefixDatum);

	if (fc_in->allTheSame)
		elog(ERROR, "allTheSame should not occur for k-d trees");

	Assert(fc_in->nNodes == 2);

	/* "which"是满足所有约束的子节点的位掩码 */
	fc_which = (1 << 1) | (1 << 2);

	for (fc_i = 0; fc_i < fc_in->nkeys; fc_i++)
	{
		Point	   *fc_query = DatumGetPointP(fc_in->scankeys[fc_i].sk_argument);
		BOX		   *fc_boxQuery;

		switch (fc_in->scankeys[fc_i].sk_strategy)
		{
			case RTLeftStrategyNumber:
				if ((fc_in->level % 2) != 0 && FPlt(fc_query->x, fc_coord))
					fc_which &= (1 << 1);
				break;
			case RTRightStrategyNumber:
				if ((fc_in->level % 2) != 0 && FPgt(fc_query->x, fc_coord))
					fc_which &= (1 << 2);
				break;
			case RTSameStrategyNumber:
				if ((fc_in->level % 2) != 0)
				{
					if (FPlt(fc_query->x, fc_coord))
						fc_which &= (1 << 1);
					else if (FPgt(fc_query->x, fc_coord))
						fc_which &= (1 << 2);
				}
				else
				{
					if (FPlt(fc_query->y, fc_coord))
						fc_which &= (1 << 1);
					else if (FPgt(fc_query->y, fc_coord))
						fc_which &= (1 << 2);
				}
				break;
			case RTBelowStrategyNumber:
			case RTOldBelowStrategyNumber:
				if ((fc_in->level % 2) == 0 && FPlt(fc_query->y, fc_coord))
					fc_which &= (1 << 1);
				break;
			case RTAboveStrategyNumber:
			case RTOldAboveStrategyNumber:
				if ((fc_in->level % 2) == 0 && FPgt(fc_query->y, fc_coord))
					fc_which &= (1 << 2);
				break;
			case RTContainedByStrategyNumber:

				/*
				 * 对于这个操作符，查询是一个盒子而不是一个点。我们在假设DatumGetPointP不会
				 * 对指向盒子的指针做任何不好的事情的程度上进行了一些作弊。
				 */
				fc_boxQuery = DatumGetBoxP(fc_in->scankeys[fc_i].sk_argument);

				if ((fc_in->level % 2) != 0)
				{
					if (FPlt(fc_boxQuery->high.x, fc_coord))
						fc_which &= (1 << 1);
					else if (FPgt(fc_boxQuery->low.x, fc_coord))
						fc_which &= (1 << 2);
				}
				else
				{
					if (FPlt(fc_boxQuery->high.y, fc_coord))
						fc_which &= (1 << 1);
					else if (FPgt(fc_boxQuery->low.y, fc_coord))
						fc_which &= (1 << 2);
				}
				break;
			default:
				elog(ERROR, "unrecognized strategy number: %d",
					 fc_in->scankeys[fc_i].sk_strategy);
				break;
		}

		if (fc_which == 0)
			break;				/* 不需要考虑其余条件 */
	}

	/* 我们必须进入由which标识的子节点 */
	fc_out->nNodes = 0;

	/* 无匹配子节点的快速路径 */
	if (!fc_which)
		PG_RETURN_VOID();

	fc_out->nodeNumbers = (int *) palloc(sizeof(int) * 2);

	/*
	 * 当指定扫描键的顺序时，我们必须为它们计算距离。
	 * 为了做到这一点，我们需要计算两个子节点的边界框。
	 * 在非零级别上计算这些边界框需要知道上层节点的边界框。
	 * 因此，我们将边界框保存到traversalValues中。
	 */
	if (fc_in->norderbys > 0)
	{
		BOX			fc_infArea;
		BOX		   *fc_area;

		fc_out->distances = (double **) palloc(sizeof(double *) * fc_in->nNodes);
		fc_out->traversalValues = (void **) palloc(sizeof(void *) * fc_in->nNodes);

		if (fc_in->level == 0)
		{
			float8		fc_inf = get_float8_infinity();

			fc_infArea.high.x = fc_inf;
			fc_infArea.high.y = fc_inf;
			fc_infArea.low.x = -fc_inf;
			fc_infArea.low.y = -fc_inf;
			fc_area = &fc_infArea;
		}
		else
		{
			fc_area = (BOX *) fc_in->traversalValue;
			Assert(fc_area);
		}

		fc_bboxes[0].low = fc_area->low;
		fc_bboxes[1].high = fc_area->high;

		if (fc_in->level % 2)
		{
			/* 按x分割盒子 */
			fc_bboxes[0].high.x = fc_bboxes[1].low.x = fc_coord;
			fc_bboxes[0].high.y = fc_area->high.y;
			fc_bboxes[1].low.y = fc_area->low.y;
		}
		else
		{
			/* 按y分割盒子 */
			fc_bboxes[0].high.y = fc_bboxes[1].low.y = fc_coord;
			fc_bboxes[0].high.x = fc_area->high.x;
			fc_bboxes[1].low.x = fc_area->low.x;
		}
	}

	for (fc_i = 1; fc_i <= 2; fc_i++)
	{
		if (fc_which & (1 << fc_i))
		{
			fc_out->nodeNumbers[fc_out->nNodes] = fc_i - 1;

			if (fc_in->norderbys > 0)
			{
				MemoryContext fc_oldCtx = MemoryContextSwitchTo(fc_in->traversalMemoryContext);
				BOX		   *fc_box = box_copy(&fc_bboxes[fc_i - 1]);

				MemoryContextSwitchTo(fc_oldCtx);

				fc_out->traversalValues[fc_out->nNodes] = fc_box;

				fc_out->distances[fc_out->nNodes] = spg_key_orderbys_distances(BoxPGetDatum(fc_box), false,
																		 fc_in->orderbys, fc_in->norderbys);
			}

			fc_out->nNodes++;
		}
	}

	/* 也设置级别增量 */
	fc_out->levelAdds = (int *) palloc(sizeof(int) * 2);
	fc_out->levelAdds[0] = 1;
	fc_out->levelAdds[1] = 1;

	PG_RETURN_VOID();
}

/*
 * spg_kd_leaf_consistent()与spg_quad_leaf_consistent()相同，
 * 因为我们支持相同的操作符和相同的叶节点数据类型。
 * 所以我们只是借用那个函数。
 */
